For any suggestions or feedback regarding these notes,
please contact Pragy Agarwal
Master-Slave Replication
Terms "Master" and "Slave" have a lot of historical baggage - and some communities don't like these words.
a.k.a.
- Leader - Follower
- Active - Passive
- Primary - Secondary
Basic Setup
Typically in Master-Slave replication, we have an odd number of total servers (replicas). Note: this is NOT mandatory, you can totally have an even number of total “replicas” as well.
Reason: With odd number of server, you have a clear majority.
Replication Factor (X): Number of total copies of the same data
(X = 1 master + slaves)
For example, if X = 3, then you have 1 master + 2 slaves
if X = 5, then you have 1 master + 4 slaves
if X = 2, then you have 1 master + 1 slave
Note: replication factor is the number of copies. It is not the total number of servers. If the database is sharded, we will have shards & replicas. A database can have S=100 shards, each shard having X=3 copies each, for a total of N=300 servers.
Typical values of X = {3, 5}
What happens if the master goes down?
A re-election will happen. One of the slaves will get elected as the new master.
What happens when the old master comes back online?
It will join as a new slave.
What if a slave crashes?
Nobody cares. Slaves die all the time.
Basically the read will go to a different slave.
How does master election happen?
Typically happens via some "distributed configuration management system" (ex. Zookeeper)
But there are other algos as well.
How do the slaves sync with the master?
Asynchronously, using Write Ahead Log
Where do the writes happen?
Always happen at least in the master.
(in some configurations, the writes can also happen in a subset of the slaves)
Where do the reads happen?
In a subset of the slaves
How many slaves?
Typically, an even number (so that the total number of servers is odd, because there’s 1 master)
Why Odd number of servers?
So that we can have a clear majority - easy to do tie breaking (in quorum)
What are the typical values of Replication Factor (X)?
We need at least 2 copies (1 master + 1 slave) — because if we have only 1 copy, there’s no replication in the first place (which will lead to data loss)
Typically we keep 3 copies of data (1 master + 2 slaves)
Sometimes you might need more
- if the data is critical and you don’t want any data loss whatsoever
set the replication factor to X = 5
Values above 5 are not used because they don’t really provide any significant benefit in terms of data loss prevention – it is already very unlike that 5 different servers from the same shard will fail at the same time. - if you’re using replication to improve the read throughput (read load can be distributed amongst the slaves), then there’s no upper limit - you can have systems with 100 replicas (but this won’t be done for the entire database; it will only be done for the cache)
- either you need immediate consistency
- you can use something write quorum / tunable consistency
- why not quorum? Because quorum worsens the read load
- write-everywhere will be bad, because there’s so many replicas
- assumption is that the write load is low enough that you can write to 98 servers before committing (very very rare)
- or you need eventual consistency
- you just write to master + 1 slave
- typically when we have so many read replicas, we need it for a “cache” and usually it is okay to be eventually consistent in this case.
Master Slave with No Consistency (data loss)
Where? | Availability | Latency | |
Reads (R = 1) | at any 1 random slave | Very High | Very Low |
Writes (W = 1) | only at the master | Very High | Very Low |
Note that the writes going to only the master doesn’t mean that slaves don’t have any data. The slaves will periodically sync-up with the master.
Instead, the master contains the latest data always, and the slaves don’t have to latest data always.
Q: Can there be data loss?
Yes.
Writes are happening only at the master. Slaves sync up with master periodically.
If the master goes down (HDD failure) with unsynced changes ⇒ these changes are lost forever!
Q: Can stale reads happen?
There can be stale reads because the slaves sync up only periodically.
Note: data loss is even worse than stale reads.
Because this config gives us data loss, we don't even care about stale reads.
Master Slave with Eventual Consistency
we will use this when eventual consistency is good enough
Where? | Availability | Latency | |
Reads (R = 1) | at any 1 random slave | Very High | Very Low |
Writes (W = 2) | Master | Decent | Decent |
Q: How are we writing to two places at the same time?
By using Two Phase Commit (2PC) — we will acquire distributed locks to ensure that this write to (master + 1 random slave) is atomic. If the write doesn’t succeed at both places, we will return an error to the client and the client can retry (meanwhile we will rollback the partial write)
Q: Can there be data loss?
No. Because the data is in at least 2 places.
What happens if the HDD fails in both the places? That will certainly lead to data loss.
What happens if Thanos attacks earth? Supernova? Black hole? ... if earth explodes, that means data loss.
HDD fails extremely rarely (once every 2-3 years). The chances that these exact two HDDs fail before the rest of the slaves can sync up is astronomically low.
Don't worry about it. It's very rare.
If we still wish to minimize your data losses, then you just write to more places.
Q: Can stale reads happen?
Yes. The reads are happening at any 1 random slave, and the slaves are not guaranteed to always have the latest data.
The latest write went to Master + Slave A, but the read went to Slave B, and the Slave B hasn’t been able to sync-up yet —- there will be a stale read.
Master Slave with Immediate Consistency - Write Everywhere
we will use this when we require immediate consistency, and the writes are rare (read heavy system)
Where? | Availability | Latency | |
Reads | at any 1 random slave | Very High | Very Low |
Writes | all nodes | Very Low | Very High |
Note that the protocol says that we must write to all X nodes. It doesn’t say that you should write to all replicas which are alive.
In write-everywhere, if even 1 replica is down, the writes have to be denied!
In write-everywhere the master's boundary is blurred. There’s basically no diff b/w the master and the slave.
Q: Can there be data loss?
No. All the copies are always in sync, and each write is replicated in multiple places.
Q: Can stale reads happen?
No. All copies are always in sync
Master Slave with Immediate Consistency - Quorum
we will use this when we require immediate consistency, and the writes are frequent (write heavy system or its a balanced system)
Idea: Improve the writes at the cost of reads. In write everywhere, the reads are very fast, but the writes are very slow. If we trade off, then both will be decent.
Where? | Availability | Latency | |
Reads | to a majority | Decent | Decent |
Writes | to a majority (atomically) | Decent | Decent |
Majority = More than half the total amount.
If the Replication Factor = X, then majority will be ceil( (x+1) / 2 )
For example, if your replication factor is X = 5, then any reads or writes must succeed at at-least 3 nodes for the request to be successful.
Q: Can there be data loss?
No. Because we’re writing to a majority, and the majority is at-least 2.
Q: Can stale reads happen?
No.
You always read the latest data, because there's at least 1 overlap (there's at least one server that you're reading from that also got the latest write)
.png)
Since different reads will return different values, we will always maintain the timestamp whenever writes happen.
And then when reading, we will return the value which has the latest timestamp.
.png)
Q: Does this mean that we’ve to synchronize the clocks across all the replicas to generate the timestamp during write?
No. The timestamp can be generated at the “coordinator” (the database app server that is coordinating the write across the various replicas)
Q: What if some servers are down? How does Quorum consider the number of servers then?
The replication factor X tells you the minimum number of copies of data you must maintain at all times. You might maintain more copies for whatever reason. Momentarily (when a replica crashes), the number of copies may fall below X. But it is the DBs responsibility to ensure that for most of the time, the number of copies remains at-least X.
What happens if a replica crashes?
Does the replication factor X change? No — the replication factor is a configuration parameter. It is not the live number of replicas.
Irrespective of how many servers have crashed, Quorum requires you to read/write successfully to at-least ceil((x+1)/2) replicas.
For example, if X = 7, so our desired majority is 4. Now imagine that 4 of the servers have crashed. In this case, no reads or writes can happen (because there’s only 3 servers remaining, but Quorum says you need to read/write to at-least 4)
Tunable Consistency - Unlocking the Spectrum Wait, there's more!?
Idea: for immediate consistency, the number of reads & writes don’t have to be equal. All we need to do is ensure that there’s an overlap.
.png)
Configurable Parameters
X = Replication Factor — minimum number of copies that must be maintained for each piece of data at all times
R = Number of Reads — minimum number of servers which must respond with data for the read to succeed
W = Number of Writes — minimum number of servers which must acknowledge the write for the write to succeed
R = 1, W = 1
same as Master-Slave with no consistency — data loss
write at master, read from any 1 random slave
No consistency, but perfect availability!
R = 1, W = 2
same as Master-Slave with eventual consistency
write at master + any 1 random slave, read from any 1 random slave
Eventual consistency, and high availability
R+W <= X, and W > 1
we will get eventual consistency
R+W > X
(the number of servers that we're writing to + the number of servers that we're reading from) is more than the total number of available servers.
⇒ there's at least one server that is being both written to and being read from – there's an overlap! (proof: pigeonhole principle)
⇒ we've immediate consistency!
R = 1, W = X ⇒ write everywhere
R = W = (X+1/2) ⇒ quorum
Since we can now choose any values of R+W, this gives us a tremendous amount of power.
If R is low ⇒ reads are faster & more available (because you're reading from only few servers)
If W is low ⇒ writes are faster & more available
If R+W > X ⇒ system is immediately consistent
As R+W increases,
- availability becomes lower, and your latency is getting higher (because you need more servers to be alive for the reads/writes to succeed)
- consistency becomes higher (because you're more likely to find an overlap - a server which you're reading from which also has the latest write)
.png)
We can not only decide our consistency, we can also tune the system for read-heavy or write-heavy operation!
In fact, we no longer are limited only to availability or consistency, we can choose any point on the spectrum!
.png)
.png)
How to write to more than one place atomically?
Two Phase Commit (2PC)
- Theory: https://www.youtube.com/watch?v=-_rdWB9hN1c
- Explanation 1: https://www.youtube.com/watch?v=eltn4x788UM
- Explanation 2: https://www.youtube.com/watch?v=7FgU1D4EnpQ
- Implementation: https://www.youtube.com/watch?v=oMhESvU87jM